package P150;

import cn.hutool.core.lang.tree.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class P59 {
    public static class TreeNode {
        int      val;
        TreeNode left;
        TreeNode right;
        TreeNode next;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null || root.left == null && root.right == null) {
            return root;
        }
        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isSymmetric(TreeNode root) {
        return isEqual(root, root);
    }

    private boolean isEqual(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return left.val == right.val && isEqual(left.left, right.right) && isEqual(left.right, right.left);
    }

    public TreeNode connect(TreeNode root) {
        if (root == null) {
            return root;
        }
        link(Collections.singletonList(root));
        return root;
    }


    public void link(List<TreeNode> list) {
        if (list.isEmpty()) {
            return;
        }
        List<TreeNode> integrate = new LinkedList<>();
        for (int i = 0; i < list.size(); i++) {
            TreeNode element = list.get(i);
            if (i + 1 < list.size()) {
                element.next = list.get(i + 1);
            }
            if (element.left != null) {
                integrate.add(element.left);
            }
            if (element.right != null) {
                integrate.add(element.right);
            }
        }
        link(integrate);
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> elementList = new ArrayList<>();
        fun(root, elementList);
        TreeNode v = new TreeNode();
        TreeNode element = v;
        for (TreeNode it : elementList) {
            element.right = it;
            element = element.right;
        }
        root = v.right;
    }

    public void fun(TreeNode root, List<TreeNode> elementList) {
        if (root == null) {
            return;
        }
        elementList.add(root);
        if (root.left != null) {
            fun(root.left, elementList);
        }
        root.left = null;
        if (root.right != null) {
            fun(root.right, elementList);
        }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        int diff = targetSum - root.val;
        if (diff < 0) {
            return false;
        }
        if (diff == 0 && root.left == null && root.right == null) {
            return true;
        }
        return hasPathSum(root.left, diff) || hasPathSum(root.right, diff);
    }

    public static int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return sum(root, 0);
    }

    public static int sum(TreeNode root, int pattern) {
        if (root == null) {
            return pattern;
        }
        int temp = pattern * 10 + root.val;
        if (root.left == null && root.right == null) {
            return temp;
        }
        int left = 0, right = 0;
        if (root.left != null) {
            left = sum(root.left, temp);
        }
        if (root.right != null) {
            right = sum(root.right, temp);
        }
        return left + right;
    }


    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        System.out.println(sum(tree, 0));
    }
}
